一.概念
对于一段区间求最优解,且该区间可以分为几个小区间的最优解合并(最优子结构)。
二.基本思路
An Ac a day, keeps the doctor away!
fi,j:两人分别在房间 i,j 的概率。初始状态 fa,b=1
fi,j=pipjfi,j+(i,u)∈E∑(j,v)∈E∑degu1−pudegv1−pvfu,v
异或的期望不能直接算,对每一位单独考虑。
f[u][0/1]:节点 u 的第 i 位为 0/1 的概率。
注意经过节点 u 的概率不一定为 1 ,所以 f[u][0]+f[u][1] 的值不一定为 1。
每一条边被选中的概率: 2n(n−1)n−1=n2
所以答案为: